#include<bits/stdc++.h>
using namespace std;
const int p=111121;
inline int qpow(int a,int b){
  if(!b)return 1;
  int r=1; a%=p;
  while(b){
    if(b&1)r=1ll*r*a%p;
    a=1ll*a*a%p,b>>=1;
  }
  return r;
}
inline void chadd(int &x,int y){
  if((x+=y)>=p)x-=p;
}
int main(){
  freopen("abstract.in","r",stdin);
  freopen("abstract.out","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,c=0; cin>>n;
  vector<int> w(n);
  for(auto &i:w)cin>>i;
  vector<vector<int> > g(n);
  for(int i=1;i<n;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  if(n<=1e4){
    for(int i=0;i<n;i++){
      function<void(int,int,int,int)> dfs=[&](int u,int f,int x,int y){
        if(u>=i)chadd(c,qpow(x,y));
        for(int j:g[u])if(j!=f)dfs(j,u,x&w[j],y|w[j]);
      };
      dfs(i,i,w[i],w[i]);
    }
  }
  cout<<c<<endl;
  return 0;
}